//https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/submissions/574414901/

class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int n = maze.size();
        int m = maze[0].size();
        int dx[] = { 0, 0, 1, -1 };
        int dy[] = { 1, -1, 0, 0 };
        bool isExport[105][105] = { 0 };
        const int N = 1e4 + 10;
        int dis[105][105];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                dis[i][j] = 1e5;
                if (i == 0 || j == 0 || i == n - 1 || j == m - 1 && (maze[i][j] == '.'))isExport[i][j] = true;
            }
        }

        queue<pair<int, int>> q;
        int sti = entrance[0];
        int stj = entrance[1];
        q.push({ sti, stj });
        isExport[sti][stj] = false;
        dis[sti][stj] = 0;

        while (q.size())
        {
            pair<int, int> now = q.front();
            int x = now.first;
            int y = now.second;
            q.pop();

            for (int i = 0; i < 4; i++)
            {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
                if (maze[nx][ny] == '+')continue;
                if (dis[nx][ny] > dis[x][y] + 1)
                {
                    dis[nx][ny] = dis[x][y] + 1;
                    q.push({ nx, ny });
                    if (isExport[nx][ny])return dis[nx][ny];
                }
            }
        }
        return -1;
    }
};